package com.caoyanan.algorithm.question.zuoTraining.training003.class08;

import com.caoyanan.algorithm.question.zuoTraining.LogarithmInputGenerator;

/**
 * 给定一个字符串，如果可以在字符串任意位置添加字符，最少添加几个能让字符串整体都是回文串。
 *
 * @author: caoyanan
 * @time: 2021/5/24 6:25 下午
 */
public class Question02_AddAnyCharToPalindrome {

    public static void main(String[] args) {

        //fbcdb 添加2个就可以？ 确实， fbdcdbf
        int count = 10000;
        for (int i = 0; i < count; i++) {
            String str = LogarithmInputGenerator.getInstance().generateLowerLetterString(5, 8);
            int number = addAnyPositionCharTOPalindrome(str.toCharArray());
            System.out.println(str+" 成为回文串至少添加 "+number+" 个字符");
        }
    }

    /**
     * 可以从任意位置添加，那么就思考，以任意位置结尾或者从一个位置到另一个位置得到回文串
     * dp[i][j]表示 从i到j得到回文串，至少需要多少个字符
     * @param str
     * @return
     */
    private static int addAnyPositionCharTOPalindrome(char[] str) {
        if (str.length == 0 || str.length == 1) {
            return 0;
        }

        int[][] dp = new int[str.length][str.length];
        //首先，对角线都是0
        for (int i = 0; i < str.length; i++) {
            dp[i][i] = 0;
        }
        //其次，左下部分没用，因为i一定小于j。
        //然后右上部分第二条对角线，如果两个字符相等，添加0个字符就是回文串，否则，添加1个。
        for (int i = 0; i < str.length-1; i++) {
            if (str[i] == str[i + 1]) {
                dp[i][i+1] = 0;
            } else {
                dp[i][i+1] = 1;
            }
        }

        //然后对于一个普遍位置i+j。
        // 首先，开头的字符和最后一个字符一样，那就是中间的子串的添加字符数，即 dp[i+1][j-1]
        // 然后就考虑需要右边补一个字符，即最左边的那个字符不是回文，然后就是取的就是除去左边第一个字符的子串的添加字符数，然后加1，即 dp[i+1][j] + 1
        // 也有可能左边补一个字符，即最右边的那个字符不是回文。那就是 dp[i][j-1]+1
        // 然后填表的时候需要斜对角向上填，不能从左向右，从上到下，因为比如dp[0][5]=dp[1][4]，这时候求0行时第一行还没有填
        // 斜着遍历的话，每一次i都是从0开始，然后j从2，3，4到str.length
        for (int outj = 2; outj < str.length; outj++) {
            int j = outj;
            for (int i = 0; j < str.length; i++, j++) {
                if (str[i] == str[j]) {
                    dp[i][j] = dp[i + 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i+1][j], dp[i][j-1]) + 1;
                }
            }
        }
        return dp[0][str.length-1];
    }
}
